/*
 * @lc app=leetcode.cn id=1 lang=typescript
 *
 * [1] 两数之和
 */

// @lc code=start
function twoSum(nums: number[], target: number): number[] {
  const size = nums.length;
  const idxs = new Array(size).fill(0).map((_, i) => i);

  // 索引排序
  idxs.sort((a, b) => nums[a] - nums[b]);

  const binarySearch = (nums: number[], idxs: number[], start: number, target: number): number => {
    let head = start;
    let tail = idxs.length - 1;
    let mid: number;
    while (head <= tail) {
      mid = head + ((tail - head) >> 1);
      if (nums[idxs[mid]] === target) return mid;
      if (nums[idxs[mid]] < target) head = mid + 1;
      else tail = mid - 1;
    }
    return -1;
  };

  const result = new Array(2);
  for (let i = 0; i < idxs.length - 1; i++) {
    const num = nums[idxs[i]];
    const j = binarySearch(nums, idxs, i + 1, target - num);
    if (j !== -1) {
      result[0] = idxs[i];
      result[1] = idxs[j];
      return result;
    }
  }

  return result;
}
// @lc code=end
